The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Networks have become an important tool for businesses and consumers alike, many of which are now dependent on the constant availability of network resources such as mail servers, Web sites, and content servers. As use of networks increases, protecting networks from disruption by malicious entities becomes more important. For example, denial of service (“DoS”) attacks may deprive legitimate users of access to network services, and have been used successfully to disrupt legitimate user access to internet sites such as Yahoo! and CNN.
“Proof-of-work” (POW) is a technique that can help defend against a spam or denial-of-service (DoS) attack in which one or more attackers marshal M machines (e.g., processing “zombies” or “bots”) to overload a resource with requests. Assume that a resource is trying to service a community of N legitimate users in addition to M attacking bots. The resource requires each machine to perform some level of “work,” such as repeatedly hashing a message until certain bits within the hash output are zero. Such techniques are described further in the references [Dwork93], [Back], [Dwork03]. If the hash function approximates a random output, then the likelihood of generating a result with k particular bits set to zero is 2^(−k), and the hash function will be repeated 2^k times on average. POW can be performed using computational work, memory-access work, or a similar commitment of practically any computer resource such as memory.
The POW defense against a DoS attack may be effective when N users have a great deal of extra capacity, and the attacking bots have dedicated all their capacities to the attack. Under these conditions, an increase in the work, w, needed to access the resource can translate into an increase in the number of bots needed to carry out an attack. For example, an increase in work of 10 w might increase the resources needed to send a mail message by 10×.
However, the POW defense has certain drawbacks. First, the legitimate user is penalized by having to perform the same amount of work as the bot, and second, the defense ultimately fails if the attacker has enough bots to out-compute the users.
As a result, there is a need for a way to prevent denial-of-service attacks on a network resource without imposing unfair penalties upon legitimate users who regularly use the resource in a proper manner.
In certain past approaches a resource seeks to authenticate a user before providing the user with access to the resource. In some such approaches, the resource requires creating a “security association” to be established between the resource and the user. In certain approaches, the user is required to exchange a cryptographic key or maintain an SSH session, TLS session or other security association with the resource.
Hash-based authentication schemes as described in [Lamport81] provide keyless techniques for authenticating users on a network. In another approach, user identification uses public-key cryptography (PKC), in which the user maintains a private key and provides the public-key portion to resources. The PKC approach, however, requires the user to maintain and exchange a cryptographic key, which many users do not do or never will do. Creating, maintaining and exchanging keys are not easy tasks for typical internet users. Moreover, PKC is not needed for conventional POW approaches.
In the description herein, the following abbreviations identify certain technical references: [Lamport81] refers to L. Lamport, “Password Authentication with Insecure Communication,” Communications of the ACM, Vol. 24, Number 11, November 1981, [Dwork92] refers to C. Dwork et al., “Pricing via Processing or Combating Junk Mail,” in Advances in Cryptology (E. Brickell, ed.), CRYPTO'92, Lecture Notes in Computer Science, LNCS 740, pp. 139-147 (Springer-Verlag, August 1992); [Back97] refers to A. Back, “Hashcash: A Denial of Service Counter Measure,” Aug. 1, 2002 (self-published); and [Dwork03] refers to C. Dwork et al., “On Memory-bound Functions for Fighting Spam,” Crypto 2003.